import java.util.*;

public class Solution207 {
    /**
     * 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
     *
     * 在选修某些课程之前需要一些先修课程。 
     * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
     *
     * 给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
     * 示例 1:
     *
     * 输入: 2, [[1,0]]
     * 输出: true
     * 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
     *
     */

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegrees = new int[numCourses];
        Map<Integer, List<Integer>> adjacency = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int[] prerequisite : prerequisites) {
            int cur = prerequisite[0];
            int pre = prerequisite[1];
            if (!adjacency.containsKey(pre)) adjacency.put(pre, new ArrayList<>());
            adjacency.get(pre).add(cur);
            inDegrees[cur]++;
        }
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()){
            int pre = queue.poll();
            numCourses--;
            if (!adjacency.containsKey(pre)) continue;
            for (int cur : adjacency.get(pre)) {
                if (--inDegrees[cur] == 0) queue.add(cur);
            }
        }
        return numCourses == 0;
    }
}
